import re

class SingleGenSqueeze:
        def __init__(self, seq, prefixLength):
                self.processed = 0;
                self.seq = self.getSequence(seq)
                self.encoded = ''
                self.prefixLength = prefixLength
            
        def update(self, matchStart, matchLength):
                code = '/' + str(matchStart) + ',' + str(matchLength)
                if len(code) >= matchLength:
                        self.encoded += self.seq[0]
                        self.processed += 1
                else:
                        self.encoded += code
                        self.processed += matchLength

        def findMatches(self):
                chunk = self.seq[self.processed : self.processed+self.prefixLength]
                # what if len(seq) < prefixLength ?
                matches = []
                match = self.seq.find(chunk, 0, self.processed)
                while match != -1:
                        matches.append(match)
                        match = self.seq.find(chunk, match+1, self.processed)
                return matches
               
        def extendMatch(self, match, mmratio):
                length = 1  # the first chars better match! (avoid / by 0)
                mismatches = 0
                start = self.processed
                n = len(self.seq)
                while start+length < n:
                        if float(mismatches)/length >= mmratio:
                                return length - 1, mismatches - 1
                        if self.seq[match + length] != self.seq[start+length]:
                                mismatches += 1
                        length += 1
                return length, mismatches

        def findLongest(self, matches, mmratio):
                bestMatch = None
                bestLength = 0
                bestMismatches = len(self.seq) # I'd use infinity if it existed
                for match in matches:
                        length, mismatches = self.extendMatch(match, mmratio)
                        if length > bestLength:
                                bestMatch = match
                                bestLength = length
                                bestMismatches = mismatches
                        elif length == bestLength and mismatches < bestMismatches:
                                bestMatch = match
                                bestLength = length
                                bestMismatches = mismatches
                return bestMatch, bestLength, bestMismatches
        
        def getSequence(self, fileinput):
                pattern = re.compile('[^actg]', re.IGNORECASE)
                match = pattern.sub('', fileinput)
                match = match.upper()
                return match

        def compress(self, mmratio = .1):
                while self.seq:
                        matches = self.findMatches()
                        start, length, mismatches = self.findLongest(matches,mmratio)
                        self.update(start, length)
                return 1.0 - float(len(self.encoded))/len(self.seq)

f = open("HUMHBB.txt")
s = f.read()
gs = SingleGenSqueeze(s, 9)
        

